/*
快速幂：
    给定a, b, p, 求a的b次方，或者求a的b次方对p取余
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll quickPow(ll a, ll b) // 不带模数
{
    ll ans = 1;
    while (b)
    {
        if (b & 1) // 判断是否为奇数or判断二进制最低位是否为1
            ans *= a;
        b >>= 1;
        a *= a;
    }
    return ans;
}
ll quickPow(ll a, ll b, ll p) // 带模数
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans;
}
int main()
{
    ll a = 5, b = 13;
    cout << "a^b = " << quickPow(a, b) << endl; // 1220703125
    b = 33;
    cout << "a^b = " << quickPow(a, b) << endl;           // 116,415,321,826,934,814,453,125
    cout << "(a^b)%p = " << quickPow(a, b, 1000) << endl; // 116,415,321,826,934,814,453,125
    return 0;
}
